import java.util.ArrayList;
import java.util.List;

// 收集累加和等于aim的所有路径
// 测试链接 : https://leetcode.cn/problems/path-sum-ii/
public class Code03_PathSumII {
    // 不提交这个类，这个内部类用于表示二叉树的节点
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    // 提交如下的方法，功能是在二叉树中找到所有从根节点到叶子节点路径上节点值之和等于aim的路径集合
    public static List<List<Integer>> pathSum(TreeNode root, int aim) {
        // 创建一个用于存储最终结果的列表，其中每个元素也是一个列表，表示满足条件的路径
        List<List<Integer>> ans = new ArrayList<>();
        // 如果根节点不为空，才开始寻找路径
        if (root!= null) {
            // 创建一个空的列表，用于临时存储当前正在构建的路径
            List<Integer> path = new ArrayList<>();
            // 调用递归函数f开始查找路径
            f(root, aim, 0, path, ans);
        }
        // 返回所有满足条件的路径集合
        return ans;
    }

    // 递归函数f，用于深度优先搜索二叉树来查找满足条件的路径
    public static void f(TreeNode cur, int aim, int sum, List<Integer> path, List<List<Integer>> ans) {
        // 如果当前节点是叶子节点（没有左子节点和右子节点）
        if (cur.left == null && cur.right == null) {
            // 检查当前路径上节点值的总和（当前节点值加上之前的总和sum）是否等于目标值aim
            if (cur.val + sum == aim) {
                // 如果等于目标值，将当前节点的值添加到当前路径列表path中
                path.add(cur.val);
                // 调用copy函数将当前路径path的副本添加到结果列表ans中
                copy(path, ans);
                // 为了回溯，将刚刚添加到路径列表path中的当前节点值移除
                // 这样可以继续探索其他可能的路径，避免路径构建错误
                path.remove(path.size() - 1);
            }
        } else {
            // 如果当前节点不是叶子节点
            // 将当前节点的值添加到当前路径列表path中
            path.add(cur.val);
            // 如果当前节点的左子节点不为空，递归调用f函数继续探索左子树
            if (cur.left!= null) {
                f(cur.left, aim, sum + cur.val, path, ans);
            }
            // 如果当前节点的右子节点不为空，递归调用f函数继续探索右子树
            if (cur.right!= null) {
                f(cur.right, aim, sum + cur.val, path, ans);
            }
            // 为了回溯，将刚刚添加到路径列表path中的当前节点值移除
            // 这是因为在探索完当前节点的子树后，需要回到上一层继续探索其他分支
            path.remove(path.size() - 1);
        }
    }

    // 这个函数的功能是将输入的路径列表path复制一份，并将副本添加到结果列表ans中
    public static void copy(List<Integer> path, List<List<Integer>> ans) {
        // 创建一个新的空列表，用于存储路径的副本
        List<Integer> copy = new ArrayList<>();
        // 遍历输入的路径列表path，将其中的每个元素添加到副本列表copy中
        for (Integer num : path) {
            copy.add(num);
        }
        // 将副本列表copy添加到结果列表ans中
        ans.add(copy);
    }
}